package com.li.algorithm.leetcode.hot100;

import java.util.*;


class Pair {
    Character letter;
    Integer position;

    public Pair(Character letter, Integer position) {
        this.position = position;
        this.letter = letter;
    }

    public Character getLetter() {
        return letter;
    }

    public Integer getPosition() {
        return position;
    }
}

/**
 * 关键是从一个模糊的、复杂度高的、难以实现的想法不断优化，不断逼近结果的过程！
 * 查询覆盖子串无法直接进行双重循环遍历对比，只能利用数组统计t的各个字母数量，然后遍历s消除t中的字母
 * 直接遍历s中的字母无法简单获取最小覆盖子串，需要利用滑动窗口
 * 如何校验当前窗口匹配成功？答：同样使用数组统计当前窗口中各个字母的数量，每次滑动过程中比较当前滑入滑出的字母数量即可
 * 但是滑动窗口时，由于s中有过多其它字母，影响匹配效率，可以提纯匹配字符串，去掉无用信息（字母），提高查询效率
 * 提纯的过程中，需要恰当设计数据结构，同时保存提纯后的字母及其在原串中的位置
 */
public class Test12 {
    public String minWindow(String s, String t) {

        int minLength = Integer.MAX_VALUE;
        char[] tChars = t.toCharArray();
        char[] sChars = s.toCharArray();

        ArrayList<Pair> pureList = new ArrayList<>();

        //t中的字符情况
        int[] tCount = new int[52];
        //统计t中每个字符的数量信息
        for (char tChar : tChars) {
            int k = Character.isUpperCase(tChar) ? tChar - 'A' : tChar - 'a' + 26;
            tCount[k]++;
        }

        //提纯s中的字符，只保留t中包含的字母， 提纯字符串中包含字母及其下标
        for (int i = 0; i < sChars.length; i++) {
            char sChar = sChars[i];
            int k = Character.isUpperCase(sChar) ? sChar - 'A' : sChar - 'a' + 26;
            if (tCount[k] > 0) {
                pureList.add(new Pair(sChar, i));
            }
        }

        //在pureList中找到第一个匹配串
        int num = 0;
        int start = 0, end = -1;
        int realStart = 0, realEnd = -1;
        int[] copyCount = Arrays.copyOf(tCount, tCount.length);
        //TODO:记录第一个匹配串中各个字符的个数
        int[] subCount = new int[52];
        for (int i = 0; i < pureList.size(); i++) {
            Character letter = pureList.get(i).getLetter();
            int k = Character.isUpperCase(letter) ? letter - 'A' : letter - 'a' + 26;
            subCount[k]++;
            if (copyCount[k] > 0) {
                copyCount[k]--;
                num++;
            }
            if (num == t.length()) {
                end = i;
                realStart = pureList.get(start).getPosition();
                realEnd = pureList.get(end).getPosition();
                break;
            }
        }
        //找不到匹配的子串
        if (end == -1) {
            return "";
        }

        //TODO: 计算第一个匹配子串的长度
        minLength = realEnd - realStart;

        //TODO: 从当前匹配成功的第一个子串，进行滑动窗口
        //TODO: 左指针先移动，查看对当前匹配是否产生影响
        //TODO:   不产生影响，继续移动左指针
        //TODO:   产生影响，移动右指针，直到该影响被弥补
        //问题：如何判断左指针上的字符是否是有效字符？
        //对比t中的字符个数count，和上述过程记录的s子串中各个字符的个数
        int i = start, j =  end;
        while (i < j) {
            //TODO: 判断 i 字符是否为有效字符
            Character letter = pureList.get(i).getLetter();
            i++;
            int k = Character.isUpperCase(letter) ? letter - 'A' : letter - 'a' + 26;
            //有效字符
            if (subCount[k] == tCount[k]) {
                int flag = 0;
                //移动j，直到替补i字符
                while (++j < pureList.size()) {
//                    j++;
                    Character subLetter = pureList.get(j).getLetter();
                    if (subLetter == letter) {
                        flag = 1;
                        break;
                    }
                    int l = Character.isUpperCase(subLetter) ? subLetter - 'A' : subLetter - 'a' + 26;
                    subCount[l]++;
                }
                //后面都没有能匹配成功的子串了
                if (flag == 0) {
                    return s.substring(realStart, realEnd+1);
                }
            }
            //无效字符，直接删除
            else {
                subCount[k]--;
            }
            //TODO:计算当前长度
            if (pureList.get(j).getPosition() - pureList.get(i).getPosition() < minLength) {
                minLength = pureList.get(j).getPosition() - pureList.get(i).getPosition();
                realStart = pureList.get(i).getPosition();
                realEnd = pureList.get(j).getPosition();
            }
        }
        return s.substring(realStart, realEnd+1);
    }

    public static void main(String[] args) {
        Test12 test12 = new Test12();
        System.out.println(test12.minWindow("ADOBECODEBANC", "ABC"));
    }
}
